package likou.tanxin;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2020/11/21 07:59
 */
public class _1090 {
    public static void main(String[] args) {
        System.out.println(largestValsFromLabels(new int[]{5,4,3,2,1},new int[]{1,1,2,2,3},3,1));
    }
    public static int largestValsFromLabels(int[] values, int[] labels, int num_wanted, int use_limit) {
        quickSort(values,labels,0,values.length-1);
        int[] num = new int[20000];
        int daan = 0;
        int k =0;
        for(int i=0;i<values.length;i++){
            int nowLab = labels[i];
            if(num[nowLab]!=use_limit){
                daan+=values[i];
                num[nowLab]++;
                k++;
                if(k==num_wanted){
                    return daan;
                }
            }
        }
        return daan;
    }
    public static void quickSort(int[] values,int[] labels,int startIndex,int endIndex){
        if(startIndex>=endIndex){
            return;
        }
        int pivot = partition(values,labels,startIndex,endIndex);
        quickSort(values,labels,startIndex,pivot-1);
        quickSort(values,labels,pivot+1,endIndex);
    }
    public static int partition(int[] values,int[] labels,int startIndex,int endIndex){
        int pivot = values[startIndex];
        int left=startIndex,right=endIndex;
        while(left<right){
            while(left<right&&values[right]<pivot){
                right--;
            }
            while(left<right&&values[left]>=pivot){
                left++;
            }
            int tem = values[right];
            values[right] = values[left];
            values[left] = tem;
            tem = labels[right];
            labels[right] = labels[left];
            labels[left] = tem;
        }
        values[startIndex] = values[left];
        values[left] = pivot;
        int pivotL = labels[startIndex];
        labels[startIndex] = labels[left];
        labels[left] = pivotL;
        return left;
    }
}
